10203. Арктическая сеть

Министерство национальной обороны (МНО) хочет соединить несколько северных форпостов беспроводной сетью. При создании сети должны использоваться две различные технологии связи: каждая застава будет иметь радиоприемник, а некоторые заставы дополнительно будут иметь спутниковый канал.

Любые два аванпоста со спутниковым каналом могут связываться через спутник, независимо от их местоположения. В противном случае два аванпоста могут общаться по радио, только если расстояние между ними не превышает d, что зависит от мощности трансиверов. Чем выше мощность, тем выше d, но стоят они больше. По соображениям покупки и обслуживания трансиверы на заставах должны быть идентичными; то есть значение d должно быть одинаковым для каждой пары форпостов.

Вам следует определить наименьшее значение d, необходимое для трансиверов. Между каждой парой аванпостов должен быть хотя бы один канал связи (прямой или косвенный).

Вход. Первая строка содержит количество n тестов. Первая строка каждого теста содержит количество спутниковых каналов s (1 ≤ s ≤ 100) и количество аванпостов p (s < p ≤ 500). Далее следуют p строк, в которых указаны координаты (x, y) каждой заставы в км (координаты – целые числа от 0 до 10000).

Выход. Для каждого теста выведите минимальное d, необходимое для подключения к сети. Вывод следует совершать с точностью до 2 десятичных знаков.

Пример входа	Пример выхода
1 2 4 1 0 3 0 6 0 7 2	2.24

РЕШЕНИЕ

графы – алгоритм Прима

Анализ алгоритма

Запустим алгоритм Прима. Построим массив dist, в котором dist[i] хранит длину кратчайшего ребра из минимального остова, входящего в вершину i. То есть как раз из этих ребер и состоит минимальный остов. При этом dist[0] = 0, так как стартуем алгоритм из вершины 0.

По окончанию алгоритма Прима отсортируем массив dist. Спутниковыми каналами следует соединить наиболее отдаленные аванпосты. Их следует разместить в тех s аванпостах, которые соединяют самые длинные ребра из dist (s – 1 ребро соединяет s аванпостов). Следовательно искомым значением d будет длина ребра, являющегося s-ым с конца dist.

Пример

Рассмотрим пример, приведенный в условии.

Два спутниковых канала ставим в точках (3; 0) и (6; 0). Таким образом заставы в этих координатах связываются через спутник. Среди оставшихся ребер минимального остовного дерева ищем наибольшее. Таким будет ребро, соединяющее точки (6; 0) и (7; 2), его длина равна 2.24.

Реализация алгоритма

Объявим глобальные массивы. Координаты застав храним в (x[i], y[i]). Значение used[i] = 1, если вершина i включена в остов.

#define MAX 501

#define INF 0x3F3F3F3F

int x[MAX], y[MAX];

int used[MAX], dist[MAX];

Функция dist2 вычисляет квадрат расстояния между заставами i и j.

int dist2(int i, int j)

{

return (x[j] - x[i])*(x[j] - x[i]) + (y[j] - y[i])*(y[j] - y[i]);

}

Функция Prim реализует алгоритм Прима.

void Prim(void)

{

Инициализируем массивы.

memset(dist, 0x3F, sizeof(dist));

memset(used, 0, sizeof(used));

Начинаем строить минимальный остов с вершины 0. Инициализируем dist[0] = 0, used[0] = 1.

int i, j, cur = 0;

dist[cur] = 0;

used[cur] = 1;

Совершаем n – 1 итерацию. На каждой итерации в остов добавляем одну вершину (так что в остов еще следует добавить n – 1 вершин).

for (i = 1; i < n; i++)

{

Текущей вершиной является cur. Перебираем ребра (cur, j) и пересчитываем значение dist[j]. Таким образом dist[j] хранит текущее кратчайшее расстояние от вершины j до текущего минимального остова.

for (j = 0; j < n; j++)

if (!used[j] && (dist2(cur, j) < dist[j]))

dist[j] = dist2(cur, j);

Ищем ребро наименьшей длины, которое будет включено в остов. Для этого ищем такое наименьшее dist[j], что вершина j еще не принадлежит остову (used[j] = 0). Номер вершины с наименьшим dist[j] заносим в cur (она становится текущей).

int min = INF;

for (j = 0; j < n; j++)

if (!used[j] && (dist[j] < min))

{

min = dist[j];

cur = j;

}

Вершина cur включается в остов.

used[cur] = 1;

}

}

Основная часть программы. Обрабатываем tests тестов.

scanf("%d", &tests);

while (tests--)

{

Читаем входные данные.

scanf("%d %d", &s, &n);

for (i = 0; i < n; i++)

scanf("%d %d", &x[i], &y[i]);

Запускаем алгоритм Прима.

Prim();

Сортируем массив dist.

sort(dist, dist + n);

Выводим ответ.

printf("%.2lf\n", sqrt(dist[n - s]));

}

Java реализация

import java.util.*;

public class Main

{

static int n;

static int x[], y[];

static int used[], dist[];

static int dist2(int i, int j)

{

return (x[j] - x[i])*(x[j] - x[i]) + (y[j] - y[i])*(y[j] - y[i]);

}

static void Prim()

{

dist = new int[n];

Arrays.fill(dist, Integer.MAX_VALUE);

used = new int[n];

int i, j, cur = 0;

dist[cur] = 0;

used[cur] = 1;

for (i = 1; i < n; i++)

{

for (j = 0; j < n; j++)

if (used[j] == 0 && dist2(cur, j) < dist[j])

dist[j] = dist2(cur, j);

int min = Integer.MAX_VALUE;

for (j = 0; j < n; j++)

if (used[j] == 0 && dist[j] < min)

{

min = dist[j];

cur = j;

}

used[cur] = 1;

}

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

while (tests-- > 0)

{

int s = con.nextInt();

n = con.nextInt();

x = new int[n];

y = new int[n];

for (int i = 0; i < n; i++)

{

x[i] = con.nextInt();

y[i] = con.nextInt();

}

Prim();

Arrays.sort(dist);

System.out.println(Math.sqrt(dist[n - s]));

}

con.close();

}

}